package Offer;

/*
    题目：
        给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋ 的元素。
        你可以假设数组是非空的，并且给定的数组总是存在多数元素。
        来源：力扣（LeetCode）
        链接：https://leetcode.cn/problems/majority-element
        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    提示：
        n == nums.length
        1 <= n <= 5 * 10^4
        -10^9 <= nums[i] <= 10^9

    进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

    思路：
       1)可以使用哈希表，存储数值及其次数的映射关系
       2)将数组进行排序，出现次数大于 ⌊ n/2 ⌋ 的元素必定在中点
       3)摩尔投票法 ———— 时间复杂度为O(n),空间复杂度为O(1)，为本题最优
         1.若记众数的票数为 +1 ，非众数的票数为 −1 ，则一定有所有数字的票数和 > 0 。
         2.若数组的前 a 个数字的 票数和 = 0 ，则数组剩余 (n−a) 个数字的票数和一定仍 >0 ，即后 (n−a) 个数字的众数还是 x
         3.根据以上推论，记数组首个元素为 n（假设它为总数） ，众数为 x，遍历并统计票数。当发生票数和 votes =0 时，
           剩余数组的众数一定不变 ，这是由于：
           (1. 如果n == x,那么被抵消的元素中有一半是众数
           (2. 如果n !=x,那么被抵消的元素中，众数的个数最少为0，最多为一半；也就是剩余元素中的众数个数还是比非众数个数多
           利用此特性，每轮假设发生 票数和 = 0 都可以 缩小剩余数组区间 。当遍历完成时，最后一轮假设的数字即为众数。
* */

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class T39_majorityElement {

    /**
     * 排序法
     * @param nums
     * @return
     */
    public int majorityElement3(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }



    /**
     * 哈希表法
     * @param nums
     * @return
     */
    public int majorityElement2(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1); //对应的个数+1
            }else { //第一次添加的时候个数为
                map.put(num, 1);
            }
        }

        //寻找个数大于 ⌊ n/2 ⌋ 的元素
        for (Map.Entry entry : map.entrySet()) {
            if ((int)entry.getValue() > nums.length / 2) {
                return (int) entry.getKey();
            }
        }

        //题目说了必定存在这样一个众数
        return -1;
    }

    /**
     * 摩尔投票法
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        int x=0, votes = 0;       // x为众数，假设初始值为0
        for (int num : nums) {

            if (votes == 0) {   //当votes为0时，可以假设num为众数
                x = num;
            }

            if (num == x) {
                votes++;
            }else {
                votes--;
            }
        }
        return x;
    }
}
